package leetcode;
/**
 * 145.二叉树的后序遍历
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 * 输入：root = [1,null,2,3]
 * 输出：[3,2,1]
 */
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
public class Num_145 {
    /** 方法一：递归 **/
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        //边界条件
        if(root == null){
            return list;
        }
        //先递归遍历左子树
        postorderTraversal(root.left);
        //再递归遍历右子树
        postorderTraversal(root.right);
        //最后添加根节点
        list.add(root.val);
        return list;
    }

    /** 方法二：迭代 **/
    public List<Integer> postorderTraversal2(TreeNode root){
        List<Integer> list = new ArrayList<>();
        //边界条件
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        //当前节点
        TreeNode cur = root;
        //上一个完全处理过(左右根)的节点
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            //先向左走到尽头
            while(cur != null){
                stack.offerFirst(cur);
                cur = cur.left;
            }
            //此时cur==null,让cur取栈顶元素
            cur = stack.pollFirst();
            //判断右树是否为null或完全处理过的节点
            if(cur.right == null || prev == cur.right){
                //说明此时左右都处理过了，添加根节点的值
                list.add(cur.val);
                //更新该节点为完全处理过的节点
                prev = cur;
                //将cur置为空，会一直递归左树进入死循环
                cur = null;
            }else{
                //此时右树不为空且未完全处理过,则继续处理右树
                stack.offerFirst(cur);
                cur = cur.right;
            }
        }
        return list;
    }
}
